package sword.chapter8Tree;

/**
 * 节点之和最大的路径
 *
 * 深度优先搜索 前序遍历
 * 要点
 * 1. 递归分别计算左右贡献值
 * 2. 计算当前节点之和路径（node.val + leftGain + rightGain），并与历史maxSum比较更新答案
 * 3. 递归返回当前节点业务处理，node.val + Math.max(leftGain, rightGain)，返回节点最大贡献值，可能是左节点，也可能是右节点
 *
 * @author K
 * @date 2021/12/8 08:56
 */
public class S51MaxPathSum {
    static int maxSum = Integer.MIN_VALUE;

    private static int maxGain(TreeNode node) {
        if (node == null) {
            return 0;
        }
        // 递归计算左右子节点的最大贡献值
        // 只有在最大贡献值大于 0 时，才会选取对应子节点
        int leftGain = Math.max(maxGain(node.left), 0);
        int rightGain = Math.max(maxGain(node.right), 0);

        // 节点的最大路径和，取决于该节点的值与该节点的左右子节点的最大贡献值
        int pathSum = node.val + leftGain + rightGain;

        // 更新答案
        maxSum = Math.max(maxSum, pathSum);

        // 返回节点的最大贡献值
        return node.val + Math.max(leftGain, rightGain);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(-9);
        TreeNode node4 = new TreeNode(4);

        TreeNode node20 = new TreeNode(20);
        TreeNode node15 = new TreeNode(15);
        TreeNode node7 = new TreeNode(7);
        TreeNode node3 = new TreeNode(-3);
        root.left = node4;
        root.right = node20;
        node20.left = node15;
        node20.right = node7;
        node15.left = node3;

        maxGain(root);
        int result2 = maxSum;
        System.out.println();
    }
}
